#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "prng.c"

typedef struct{
      int ponto;
      struct Cobertura *prox;
} Cobertura;



double *custo_estacao;
Cobertura * cobertura;

      /*        N 9
                M 5
                S1 1 1 2 3 4 5 6 7 8 9
                S2 3 1 2 3 4
                S3 5 5 6 7 8 9
                S4 7 1 3 5 7 9 
                S5 9 2 4 6 8 
       */




int solucaoValida(int n, int m, int* solucao, Cobertura* cobertura) {
    int a, ok, i,j, aux, aux2;
    int coberto[n];
    Cobertura* c;
    
    /* Iniciando vetor de contole de pontos cobertos - no inicio nenhum ponto esta coberto */
    for(i=1; i <= n; i++) {  coberto[i]=0;   }
 
    /* Percore o numero maximo de itens (ESTACOES) possivel no vetor solucao */
    for(i=0; i < m; i++) {
             // Se encontrar valor negativo em vetor de solucao, finaliza iteracoes no for..
             if (solucao[i] < 0 ) break;
             aux = solucao[i]; // Obtem numero da estacao
             //printf("NUMERO ESTACAO %d\n", aux);
             
             /* Percorre a lista referente a estacao aux */
             c = (Cobertura*)cobertura[aux].prox; // Posiciona estacao
             
             for(j=0; j < n; j++) { // Percore a principio o maximo possivel de itens (PONTOS).
                      if(c->ponto < 0) break; // Se encontrar valor negativo, indica fim da lista de itens cobertos.
                      aux2 = c->ponto;
                      //printf("   NUMERO PONTO %d\n", aux2);
                      
                      // Marcando vetor de elementos visitados 
                      coberto[aux2]=1;
                        
                      // Todos os pontos ainda nao foram cobertos
                      c = (Cobertura *)c->prox;
             }
                                  
              // Verifica se todos os pontos ja foram percorridos 
              ok=1;    // Controle se todos os pontos foram cobertos - Considera que SIM a principio.
              for(a=1; a <= n; a++) {  
                     if (coberto[a]==0) {
                           ok=0; // Encontrou solucao nao coberta, finaliza o for e sobe para o for superior..
                           break; // 
                       }
              }
              if (ok == 1) { // Se OK nao recebeu nenhuma atribuicao 0, significa a solucao cobre todos os pontos.
                    return 1; // Todos os pontos cobertos! Solucao Válida!!    
                   
              } 
    } 
    
      
    return 0; // Solucao nao COBRE todos os pontos
}






// m-5-numero de estacoes    n-9-numero de pontos a serem cobertos
int *gerar_solucao_inicial(int n, int m, Cobertura *cobertura){ //n = numero de areas a serem cobertas, m = numero de estacoes

	int* area_coberta = (int*)malloc(n*sizeof(int));
	int* solucao = (int*)malloc(m*sizeof(int));
	int j;
	// vetor que indica se uma determinada area ja foi coberta pela solucao ou nao, incializa com valores 0
	for (j=0; j<n;j++)
		area_coberta[j] =0;

	for (j=0; j<m;j++)
		solucao[j] = -1;


	int ok=0;
	int flag=0;

	do{
         	// Verifica Validade da Solucao Gerada 
           	//ok = solucaoValida(n, m, solucao, cobertura);

		// escolhe um número aleatório
		double i = prng_get_double();
		i = i*(m-1);
		int aleatorio = i;
		printf ("aleatorio = %d\n", aleatorio);

		//verifica cobertura
		int cob;
		Cobertura *aux;
		int index=0;
		aux = &cobertura[aleatorio];	
		//printf ("aux = %d\n", aux->ponto);
		int v=0;
		for (j=0; j<n; j++){
			cob = aux->ponto;
			cob--;
			//printf ("cob = %d\n", cob);	//pegando o ultimo ponto da lista ligada
			area_coberta[cob] = 1;		
			aux=(void*)aux->prox;	
			if (aux == NULL)			
				break;	
			//printf ("aux = %d\n", aux->ponto);	//pegando o ultimo ponto da lista ligada
			//printf ("area coberta = %d\n", area_coberta[cob]);	//pegando o ultimo ponto da lista ligada
		}


		//verifica se a estacao aleatorio ja faz parte da solucao
		for (v=0;v<n;v++){
			//printf ("m = %d  aleatorio = %d", m, aleatorio);
			if (solucao[v] != aleatorio && solucao[v] != -1){
				continue;
			} else if(solucao[v] == aleatorio && solucao[v] != -1){
				break;
			} else if(solucao[v] == aleatorio && solucao[v] == -1){
				break;
			} else if(solucao[v] != aleatorio && solucao[v] == -1){
				solucao[v] = aleatorio;
				break;
			}
		}


		//for (v=0;v<n;v++)
			//printf ("%d ", area_coberta[v]);	//pegando o ultimo ponto da lista ligada
		
		printf ("\n");


//		int ponto_coberto = aux->ponto;
//		printf ("ponto_coberto = %d\n", ponto_coberto);
//		flag++;
		ok =0;
		// verifica se area_coberta já totalmente coberta
		for (j=0; j<n ;j++){
			printf ("%d ", area_coberta[j]);
			if (area_coberta[j] == 1){
				ok++;			
			}
			if (ok == n)				
				flag = 1;
		}  

	}while (flag == 0);
	

int v;
			printf ("solucao :");

	 	for (v=0;v<n;v++){
			printf ("%d ", solucao[v]);
		}
		
			printf ("\n");

	return solucao;
}


//*******************************//
//*******************************//
/********* Main de teste *********/
//*******************************//
//*******************************//

/* REMOVER DEPOIS */

/* Main de teste */

void inserirNoFim(Cobertura* raiz, int numero){
    Cobertura *novo, *aux;
    novo = malloc(sizeof(Cobertura));
    if(novo == NULL) exit(0);
    novo->ponto = numero;
    novo->prox = NULL;
 
    if(raiz == NULL){
        raiz = novo;
    }else{
        aux = raiz;
        while(aux->prox != NULL){
            aux = (Cobertura*)aux->prox;
        }
        aux->prox = (void*)novo;
    }
}

Cobertura * inserirNoInicio(Cobertura * raiz, int numero){
    Cobertura * novo, *aux;
    aux = raiz;
    novo = (Cobertura *) malloc( sizeof(Cobertura) );
    if(novo == NULL) exit(0);     
    novo->ponto = numero;
    novo->prox = aux->prox;
    aux->prox = (void*)novo;
    return(aux);
}

Cobertura * cria_lista(Cobertura * raiz){     /*Função do tipo apontador para lista, i.e., o tipo de função tem de ser igual ao tipo que retorna*/
    Cobertura * novo,*aux;
 
    novo = (Cobertura *) malloc( sizeof(Cobertura ));   /*Aloca memória do tamanho de uma célula*/
 
    if(novo == NULL) exit(0);    /*Se não alocar memória significa que não há memoria disponível, logo deve sair*/
 
    aux = raiz;                /*Corrige os apontadores de forma a retornar um apontador para a célula vazia*/
    aux->prox = (void*)novo;
    novo->prox = NULL;         /*Como esta deve ser a primeira função a ser executada, esta célula vazia aponta para NULL*/
    novo->ponto=-1;
    return (aux);
}
    

int main(){
     
      double* custos_estacoes, custo_total;
      int* solucao, solucao2;
      int i, j;
      int m=5;
      int n=9;

         
      Cobertura *raiz, *aux;
      Cobertura * cobertura;
      cobertura = malloc(m*sizeof(Cobertura));
      
    
      /* 
       *  EXEMPLO DE TESTE
       *        N 9
                M 5
                S1 1 1 2 3 4 5 6 7 8 9
                S2 3 1 2 3 4
                S3 5 5 6 7 8 9
                S4 7 1 3 5 7 9 
                S5 9 2 4 6 8 
       */

      /* Gerando estacao 1 */
      raiz = (Cobertura *) malloc( sizeof(Cobertura) ); 
      raiz = (void*)cria_lista( raiz );   
      for (i=1; i<=n; i++) { inserirNoInicio(raiz, i); }
      cobertura[0].prox = (void*)raiz->prox;
      cobertura[0].ponto = 1;
      aux = (void*)cobertura[0].prox;
      //printf("Estacao 1: %d\n\n",aux->ponto);
        
        /* Gerando estacao 2 */
      raiz = (Cobertura *) malloc( sizeof(Cobertura) ); 
      raiz = (void*)cria_lista( raiz );     
      for (i=1; i<=n/2; i++) { inserirNoInicio(raiz, i); }
      cobertura[1].prox = (void*)raiz->prox;
      cobertura[1].ponto = 2;
      aux = (void*)cobertura[1].prox;
      //printf("Estacao 2: %d\n\n",aux->ponto);


        /* Gerando estacao 3 */
      raiz = (Cobertura *) malloc( sizeof(Cobertura) ); 
      raiz = (void*)cria_lista( raiz );     
      for (i=5; i<=n; i++) { inserirNoInicio(raiz, i); }
      cobertura[2].prox = (void*)raiz->prox;
      cobertura[2].ponto = 3;
      aux = (void*)cobertura[2].prox;
      //printf("Estacao 3: %d\n\n",aux->ponto);

        /* Gerando estacao 4 */
      raiz = (Cobertura *) malloc( sizeof(Cobertura) ); 
      raiz = (void*)cria_lista( raiz );     
      inserirNoInicio(raiz, 1);
      inserirNoInicio(raiz, 3);
      inserirNoInicio(raiz, 5);
      inserirNoInicio(raiz, 7);
      inserirNoInicio(raiz, 9);            
      cobertura[3].prox = (void*)raiz->prox;
      cobertura[3].ponto = 4;
      aux = (void*)cobertura[3].prox;
      //printf("Estacao 4: %d\n\n",aux->ponto);



        /* Gerando estacao 5 */
      raiz = (Cobertura *) malloc( sizeof(Cobertura) ); 
      raiz = (void*)cria_lista( raiz );     
      inserirNoInicio(raiz, 2);
      inserirNoInicio(raiz, 4);
      inserirNoInicio(raiz, 6);
      inserirNoInicio(raiz, 8);         
      cobertura[4].prox = (void*)raiz->prox;
      cobertura[4].ponto = 3;
      aux = (void*)cobertura[4].prox;
      //printf("Estacao 5: %d\n\n",aux->ponto);




      // Gerando uma solucao inicial para teste
      solucao = malloc(m*sizeof(int));
      for (i=0; i<m; i++) { 
                solucao[i] = i+2; 
               // printf("%i\n", solucao[i]);    
      }
      
      custos_estacoes = malloc(m*sizeof(double)); // simulando 5 estacoes
      for (j=0; j<m; j++) {
           custos_estacoes[j] = j*2+1; 
          // printf("%f\n", custos_estacoes[j]);    
      }
      
      printf("----------------------------------------------\n\n");
      
    
    int* sol_inicial;
    sol_inicial = malloc(m*sizeof(int));
// m-5-numero de estacoes    n-9-numero de pontos a serem cobertos
    sol_inicial = gerar_solucao_inicial(n, m, cobertura);

      
      return 0;
}
